<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>数据结构 | Hexo</title>
  <meta name="keywords" content="">
  <meta name="description" content="数据结构 | Hexo">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构">
<meta property="og:url" content="http://yoursite.com/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171844-136893.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/203103-111988.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171839-101678.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/200119-510473.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/05/113954-515448.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/203146-263519.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153239-688589.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153248-836462.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153259-101399.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/11/113055-306258.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/151817-474283.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/103950-168345.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/105245-140913.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153313-134836.png">
<meta property="article:published_time" content="2021-03-11T16:00:00.000Z">
<meta property="article:modified_time" content="2021-03-11T07:19:09.038Z">
<meta property="article:author" content="MOLU">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.1.0" rel="stylesheet">

<link href="/css/hl_theme/github.css?v=1.1.0" rel="stylesheet">

<link href="//cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" rel="stylesheet">

<script src="//cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="/js/titleTip.js?v=1.1.0" ></script>

<script src="//cdn.jsdelivr.net/npm/highlightjs@9.16.2/highlight.pack.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js"></script>



<script src="//cdn.jsdelivr.net/npm/jquery.cookie@1.4.1/jquery.cookie.min.js" ></script>

<script src="/js/iconfont.js?v=1.1.0" ></script>

<meta name="generator" content="Hexo 5.0.0"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="">
  <input class="theme_blog_path" value="">
  <input id="theme_shortcut" value="true" />
</div>


<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>MOLU</span>
</div>

<div class="icon">
    
        
        <a title="rss" href="/atom.xml" target="_blank">
            
                <i class="iconfont icon-rss"></i>
            
        </a>
        
    
        
        <a title="github" href="https://github.com/molu-ggg" target="_blank">
            
                <i class="iconfont icon-github"></i>
            
        </a>
        
    
        
    
        
    
        
        <a title="email" href="mailto:2572876783@qq.com" target="_blank">
            
                <i class="iconfont icon-email"></i>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active" data-rel="All">All<small>(35)</small></div></li>
    
        
            
            <li><div data-rel="AI论文">AI论文<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="专业知识">专业知识<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="数学">数学<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="机器学习">机器学习<small>(12)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="经典算法">经典算法<small>(10)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/about">About</a><a style="width: 50%"  class="friends">Friends</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="35">

<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        Links
        <i class="iconfont icon-left"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <div class="right-top">
        <div id="default-panel">
            <i class="iconfont icon-search" data-title="搜索 快捷键 i"></i>
            <div class="right-title">All</div>
            <i class="iconfont icon-file-tree" data-title="切换到大纲视图 快捷键 w"></i>
        </div>
        <div id="search-panel">
            <i class="iconfont icon-left" data-title="返回"></i>
            <input id="local-search-input" />
            <label class="border-line" for="input"></label>
            <i class="iconfont icon-case-sensitive" data-title="大小写敏感"></i>
            <i class="iconfont icon-tag" data-title="标签"></i>
        </div>
        <div id="outline-panel" style="display: none">
            <div class="right-title">大纲</div>
            <i class="iconfont icon-list" data-title="切换到文章列表"></i>
        </div>
    </div>

    <div class="tags-list">
    <input id="tag-search" />
    <div class="tag-wrapper">
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>50</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>AI</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>数据结构，最短路径，图</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>机器学习</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>相似度计算</a>
            </li>
        
    </div>

</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class="All 经典算法 "
           href="/2020/07/20/b_leetcode/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="leetcode &amp; 蓝桥">leetcode &amp; 蓝桥</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a id="top" class="All AI论文 "
           href="/2020/07/10/d_GAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAT">GAT</span>
            <span class="post-date" title="2020-07-10 08:50:20">2020/07/10</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="计算机组成原理">计算机组成原理</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数据结构">数据结构</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/12/05/b_%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B8%8E%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划记忆化">动态规划记忆化</span>
            <span class="post-date" title="2020-12-05 00:00:00">2020/12/05</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/25/d_300-paperDAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="DAT for recommender">DAT for recommender</span>
            <span class="post-date" title="2020-07-25 08:50:20">2020/07/25</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="算法总结">算法总结</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E6%95%B0%E5%AD%A6/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数学">数学</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All "
           href="/2020/07/05/%E5%AF%B9%E9%9A%90%E7%A7%98%E7%9A%84%E8%A7%92%E8%90%BD%E7%94%B5%E8%A7%86%E5%89%A7%E7%9A%84%E6%84%9F%E6%82%9F%E4%BB%A5%E5%8F%8A%E8%AE%A4%E8%AF%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="对隐秘的角落电视剧的感悟以及认识">对隐秘的角落电视剧的感悟以及认识</span>
            <span class="post-date" title="2020-07-05 00:00:00">2020/07/05</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/07/04/a_%E6%A8%A1%E6%9D%BF%E5%BA%93/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="模板库">模板库</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/07/04/a_%E7%99%BE%E5%BA%A6%E6%8A%80%E6%9C%AF%E8%AE%A4%E8%AF%81/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="百度技术认证">百度技术认证</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/01/d_GCN%E8%AE%BA%E6%96%87%E8%A7%A3%E8%AF%BB/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GCN">GCN</span>
            <span class="post-date" title="2020-07-01 08:50:20">2020/07/01</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/06/04/d_word2vec_node2vec/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Word2vec &amp; Node2vec">Word2vec &amp; Node2vec</span>
            <span class="post-date" title="2020-06-04 08:50:20">2020/06/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/05/05/d_GAN/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAN">GAN</span>
            <span class="post-date" title="2020-05-05 08:50:20">2020/05/05</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/05/04/d_Deepwalk/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="DEEPWALK">DEEPWALK</span>
            <span class="post-date" title="2020-05-04 08:50:20">2020/05/04</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/15/b_%E8%B4%AA%E5%BF%83/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="贪心与动态规划">贪心与动态规划</span>
            <span class="post-date" title="2020-02-15 00:00:00">2020/02/15</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/02/12/a_2020/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="机器学习零散知识记录">机器学习零散知识记录</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/12/b_%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划——背包问题">动态规划——背包问题</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/03/b_%E8%93%9D%E6%A1%A5%E6%9D%AF%E7%BB%83%E4%B9%A0%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="蓝桥杯">蓝桥杯</span>
            <span class="post-date" title="2020-02-03 00:00:00">2020/02/03</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/01/20/c_%E5%86%B3%E7%AD%96%E6%A0%91/"
           data-tag="50"
           data-author="" >
            <span class="post-title" title="决策树总结">决策树总结</span>
            <span class="post-date" title="2020-01-20 00:00:00">2020/01/20</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/01/12/b_%E5%85%A8%E6%8E%92%E5%88%97/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="全排列">全排列</span>
            <span class="post-date" title="2020-01-12 00:00:00">2020/01/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/12/02/b_%E6%9C%89%E7%A9%B7%E8%87%AA%E5%8A%A8%E6%9C%BA/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="有穷自动机">有穷自动机</span>
            <span class="post-date" title="2019-12-02 00:00:00">2019/12/02</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/11/20/b_%E9%94%99%E6%8E%92%E5%85%AC%E5%BC%8F/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="错排公式">错排公式</span>
            <span class="post-date" title="2019-11-20 00:00:00">2019/11/20</span>
        </a>
        
        <a  class="All "
           href="/2019/10/29/a_%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7/"
           data-tag="数据结构，最短路径，图"
           data-author="" >
            <span class="post-title" title="最短路径之弗洛伊德算法">最短路径之弗洛伊德算法</span>
            <span class="post-date" title="2019-10-29 00:00:00">2019/10/29</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/04/c_BPR/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="贝叶斯">贝叶斯</span>
            <span class="post-date" title="2019-08-04 08:50:20">2019/08/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/02/c_matrix/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="矩阵分解与正则化">矩阵分解与正则化</span>
            <span class="post-date" title="2019-08-02 08:25:59">2019/08/02</span>
        </a>
        
        <a  class="All "
           href="/2019/07/28/c_coordination1/"
           data-tag="AI,机器学习,相似度计算"
           data-author="" >
            <span class="post-title" title="协同过滤-上">协同过滤-上</span>
            <span class="post-date" title="2019-07-28 08:25:59">2019/07/28</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/26/c_cnn/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="cnn">cnn</span>
            <span class="post-date" title="2019-07-26 18:54:51">2019/07/26</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_coordination2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="协同过滤—下">协同过滤—下</span>
            <span class="post-date" title="2019-07-22 18:54:26">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_kmeans/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="K-means算法">K-means算法</span>
            <span class="post-date" title="2019-07-22 18:53:07">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/21/c_nerve2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络-下">神经网络-下</span>
            <span class="post-date" title="2019-07-21 11:37:18">2019/07/21</span>
        </a>
        
        <a  class="All "
           href="/2019/07/20/c_nerve1/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络—上">神经网络—上</span>
            <span class="post-date" title="2019-07-20 17:29:10">2019/07/20</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/22/c_gradient/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归与梯度下降算法">线性回归与梯度下降算法</span>
            <span class="post-date" title="2019-06-22 08:26:36">2019/06/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/19/c_flyback/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归">线性回归</span>
            <span class="post-date" title="2019-06-19 00:00:00">2019/06/19</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/05/20/b_%E8%A7%86%E9%A2%91%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="简单入门算法">简单入门算法</span>
            <span class="post-date" title="2019-05-20 00:00:00">2019/05/20</span>
        </a>
        
        <div id="no-item-tips">

        </div>
    </nav>
    <div id="outline-list">
    </div>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div id="post">
    <div class="pjax">
        <article id="post-数据结构" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">数据结构</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            <i class="iconfont icon-category"></i>
            
            
            <a  data-rel="专业知识">专业知识</a>
            
        </span>
        
        
    </div>
    <div class="article-meta">
        
            Created At : <time class="date" title='Updated At: 2021-03-11 15:19:09'>2021-03-12 00:00</time>
        
    </div>
    <div class="article-meta">
        
        
        <span id="busuanzi_container_page_pv">
            Views 👀 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%BA%8C%E7%AB%A0-%E7%BA%BF%E6%80%A7%E8%A1%A8"><span class="toc-text">第二章 线性表</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#2-1-%E9%A1%BA%E5%BA%8F%E8%A1%A8%E4%B8%8E%E9%93%BE%E5%BC%8F%E8%A1%A8%E7%9A%84%E5%8C%BA%E5%88%AB"><span class="toc-text">2.1 顺序表与链式表的区别</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-2-%E5%A4%B4%E6%8C%87%E9%92%88%E4%B8%8E%E5%A4%B4%E7%BB%93%E7%82%B9-%E9%A6%96%E5%85%83%E7%BB%93%E7%82%B9"><span class="toc-text">2.2 头指针与头结点,首元结点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-3-%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C%EF%BC%9A"><span class="toc-text">2.3 顺序表的基本操作：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-4-%E9%93%BE%E8%A1%A8%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C%EF%BC%9A"><span class="toc-text">2.4 链表基本操作：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-5-%E6%80%A7%E8%83%BD%E6%AF%94%E8%BE%83"><span class="toc-text">2.5 性能比较</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-6-%E5%85%B6%E4%BB%96%E5%B0%8F%E7%9F%A5%E8%AF%86%E7%82%B9"><span class="toc-text">2.6 其他小知识点</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%B8%89%E7%AB%A0-%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97"><span class="toc-text">第三章 栈与队列</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#3-1-%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%9A%84%E5%8C%BA%E5%88%AB"><span class="toc-text">3.1 栈与队列的区别</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-2-%E6%A0%88%E7%9A%84%E7%9F%A5%E8%AF%86%E7%82%B9"><span class="toc-text">3.2 栈的知识点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-3-%E9%98%9F%E5%88%97%E7%9A%84%E7%9F%A5%E8%AF%86%E7%82%B9"><span class="toc-text">3.3 队列的知识点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-4-%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%9A%84%E5%BA%94%E7%94%A8"><span class="toc-text">3.4 栈与队列的应用</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E5%9B%9B%E7%AB%A0-%E4%B8%B2"><span class="toc-text">第四章 串</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#4-1-%E4%B8%B2%E7%9A%84%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F"><span class="toc-text">4.1 串的存储方式</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-2-KMP%E7%AE%97%E6%B3%95"><span class="toc-text">4.2 KMP算法</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%BA%94%E7%AB%A0-%E6%A0%91"><span class="toc-text">第五章 树</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#5-1-%E6%A0%91%EF%BC%9A"><span class="toc-text">5.1 树：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-2-%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">5.2 二叉树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-3-%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%8C%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">5.3 遍历二叉树，线索二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#5-3-1-%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">5.3.1 遍历二叉树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-3-2-%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">5.3.2 线索二叉树</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-4-%E6%8E%92%E5%BA%8F%E4%BA%8C%E5%8F%89%E6%A0%91-%E4%B8%8E%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">5.4 排序二叉树 与平衡二叉树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-5-%E6%A0%91%E6%A3%AE%E6%9E%97"><span class="toc-text">5.5 树森林</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-6-%E6%A0%91%E7%9A%84%E5%AD%98%E5%82%A8"><span class="toc-text">5.6 树的存储</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-7-%E6%A0%91%E7%9A%84%E5%BA%94%E7%94%A8"><span class="toc-text">5.7 树的应用</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E5%85%AD%E7%AB%A0-%E5%9B%BE"><span class="toc-text">第六章 图</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#6-1-%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84"><span class="toc-text">6.1 存储结构</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#6-2-%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86"><span class="toc-text">6.2 图的遍历</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#6-3-%E5%9B%BE%E7%9A%84%E5%BA%94%E7%94%A8"><span class="toc-text">6.3 图的应用</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#6-3-1-%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91"><span class="toc-text">6.3.1 最小生成树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-3-2-%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84"><span class="toc-text">6.3.2  最短路径</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-3-4-%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F"><span class="toc-text">6.3.4 拓扑排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-3-4-%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84"><span class="toc-text">6.3.4 关键路径</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-3-5-%E6%9C%89%E5%90%91%E6%97%A0%E5%90%91%E5%9B%BE%E6%8F%8F%E8%BF%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F"><span class="toc-text">6.3.5 有向无向图描述表达式</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%B8%83%E7%AB%A0-%E6%9F%A5%E6%89%BE"><span class="toc-text">第七章 查找</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#7-1-%E9%A1%BA%E5%BA%8F%E4%B8%8E%E6%8A%98%E5%8D%8A%E6%9F%A5%E6%89%BE"><span class="toc-text">7.1 顺序与折半查找</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#7-2-%E5%88%86%E5%9D%97%E6%9F%A5%E6%89%BE"><span class="toc-text">7.2 分块查找</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#7-3-B%E6%A0%91%EF%BC%88%E5%A4%9A%E8%B7%AF%E5%B9%B3%E8%A1%A1%E6%9F%A5%E6%89%BE%E6%A0%91%EF%BC%89"><span class="toc-text">7.3 B树（多路平衡查找树）</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#7-4-B-%E6%A0%91"><span class="toc-text">7.4 B+ 树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#7-5-%E6%95%A3%E5%88%97%E8%A1%A8%EF%BC%9A"><span class="toc-text">7.5 散列表：</span></a></li></ol></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-4 i,
    .toc-level-4 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="第二章-线性表"><a href="#第二章-线性表" class="headerlink" title="第二章 线性表"></a>第二章 线性表</h1><p>线性表：表内数据类型相同，有限序列</p>
<p>本章将以总结的形式展现：</p>
<h2 id="2-1-顺序表与链式表的区别"><a href="#2-1-顺序表与链式表的区别" class="headerlink" title="2.1 顺序表与链式表的区别"></a>2.1 顺序表与链式表的区别</h2><div class="table-container">
<table>
<thead>
<tr>
<th></th>
<th>顺序表</th>
<th>链式表</th>
</tr>
</thead>
<tbody>
<tr>
<td>存取</td>
<td>随机存取</td>
<td>顺序存取</td>
</tr>
<tr>
<td>结构</td>
<td>顺序存储（连续）</td>
<td>随机存储（不连续）</td>
</tr>
<tr>
<td>空间分配</td>
<td>静态存储（可以动态分配）</td>
<td>动态存储</td>
</tr>
<tr>
<td>操作</td>
<td><strong>查找 O(1) ,插入和删除O（n）</strong></td>
<td><strong>查找 O(n) ,插入和删除O（1）</strong></td>
</tr>
<tr>
<td>缺点</td>
<td>插入删除不便，长度不可以改变</td>
<td>查找速度慢，占用空间大（存储指针）</td>
</tr>
</tbody>
</table>
</div>
<h2 id="2-2-头指针与头结点-首元结点"><a href="#2-2-头指针与头结点-首元结点" class="headerlink" title="2.2 头指针与头结点,首元结点"></a>2.2 头指针与头结点,首元结点</h2><p>头指针指向链表的第一个节点（不管是否含有头结点）</p>
<p>头结点：不存储信息或者存储特殊信息的结点，好处是：</p>
<p>① 便于基本操作，第一个有数据的结点与后面的处理方式一样，不用特殊处理</p>
<p>② 链表是否为空，头指针都指向头结点</p>
<p>首元结点：</p>
<p>第一个含有 数据元素的结点</p>
<h2 id="2-3-顺序表的基本操作："><a href="#2-3-顺序表的基本操作：" class="headerlink" title="2.3 顺序表的基本操作："></a>2.3 顺序表的基本操作：</h2><p>插入删除要考虑的：</p>
<p>是否越界（插入位置不合理） ，是否（空、满）</p>
<p>:100: </p>
<h2 id="2-4-链表基本操作："><a href="#2-4-链表基本操作：" class="headerlink" title="2.4 链表基本操作："></a>2.4 链表基本操作：</h2><p>头插法与尾插法：</p>
<p>头插法：插入表头之后，插得越早越在后面</p>
<p>尾插法：链表顺序与插入的顺序一致</p>
<p>单链表与循环链表删除节点的操作</p>
<pre><code class="lang-c++">p-&gt; next = Null//是否为空
p  =  getElem(L,i-1)// 寻找前继结点
q = p-&gt;next// 将待删除节点的值临时保存
p-&gt;next = p-&gt;next -&gt;next// 删除
free(q)// 释放
</code></pre>
<p>注意：若循环链表删除的结点的后一个结点的操作 是一样的操作</p>
<p>双链表操作：</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png" alt="img"></p>
<p>插入：（有几种插入顺序）</p>
<pre><code class="lang-c++">s-&gt;next = p-&gt;next 
p-&gt;next -&gt;prior = s
p-&gt;next = s 
s-&gt;prior = p
</code></pre>
<p>注意：插入方式不唯一，保证 1,2要在3之前完成</p>
<p>这样就有 ： 1,2,3,4,1,2,4,3；2,1,3,4；2,1,4,3；</p>
<p>​                    1,4,2,3；4,1,2,3；2,4,1,3；4,2,1,3；</p>
<p>:100: 答案有待验证</p>
<p>删除：</p>
<pre><code class="lang-c">p-&gt;next = q-&gt;next;
q-&gt;next -&gt;prior = p ;
free(q);
</code></pre>
<p>:100: 代码实现：</p>
<h2 id="2-5-性能比较"><a href="#2-5-性能比较" class="headerlink" title="2.5 性能比较"></a>2.5 性能比较</h2><p>主要从空间与时间复杂度两个角度</p>
<p>是衡量一个算法好坏的必备 要素 </p>
<h2 id="2-6-其他小知识点"><a href="#2-6-其他小知识点" class="headerlink" title="2.6 其他小知识点"></a>2.6 其他小知识点</h2><ul>
<li>:100:动态分配：不需要一次性为线性表一次性划分所有空间，<strong>而是根据申请的最大空间，</strong> 一旦数据结构空间占满，就会开辟一块更大的存储空间，用来替换原来的存储空间，从而达到扩充存储空间的目的 。并不是链式存储，而是随机存取方式</li>
<li></li>
</ul>
<h1 id="第三章-栈与队列"><a href="#第三章-栈与队列" class="headerlink" title="第三章 栈与队列"></a>第三章 栈与队列</h1><h2 id="3-1-栈与队列的区别"><a href="#3-1-栈与队列的区别" class="headerlink" title="3.1 栈与队列的区别"></a>3.1 栈与队列的区别</h2><div class="table-container">
<table>
<thead>
<tr>
<th></th>
<th>栈</th>
<th>队列</th>
</tr>
</thead>
<tbody>
<tr>
<td></td>
<td>先进后出</td>
<td>先进先出</td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
</tr>
<tr>
<td>遍历速度</td>
<td>栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性。</td>
<td>队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多</td>
</tr>
<tr>
<td></td>
<td></td>
</tr>
</tbody>
</table>
</div>
<p>:100: <a target="_blank" rel="noopener" href="https://zhidao.baidu.com/question/223432364.html">https://zhidao.baidu.com/question/223432364.html</a> 没太看懂</p>
<h2 id="3-2-栈的知识点"><a href="#3-2-栈的知识点" class="headerlink" title="3.2 栈的知识点"></a>3.2 栈的知识点</h2><ul>
<li><p>卡特兰数：</p>
<p>n个不同元素进栈，出战元素不同进栈顺序可以为：$1/(n+1) C_{2n}^{n}$</p>
</li>
<li><p>顺序栈：</p>
<p>进栈操作：栈不满，栈顶指针先+1 再奖值送到栈顶元素里</p>
<p>出栈操作：栈非空，取出栈顶元素，指针 -1  （这里的1指的是一个单位）</p>
</li>
<li><p>共享栈：</p>
</li>
</ul>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/23/171844-136893.png" alt="image-20210219201351205"></p>
<p>​    栈空与栈满的判断条件：</p>
<p>​    左： top0 =-1 右：top1 = Maxsize </p>
<p>​    栈满： top1-top0 = 1 </p>
<ul>
<li><p>如何判断出栈顺序是否合理？ p70页自己总结：</p>
<p>相对位置靠前的，必定逆序，其他的没有要求</p>
</li>
<li><p>链式栈：</p>
<p> 入栈操作：（前插法）</p>
<pre><code class="lang-c++">//假设指针top指向栈顶，p是表头，q新建空间
q-&gt;next = top (p-&gt;next)
p-&gt;next = q ;
top--;
</code></pre>
<p>出栈：</p>
<pre><code class="lang-c++、、">if (s==NULL) return 0 ;//判断是否为空
x = s-&gt;data;//保存
p =s ; //保存
s =s-&gt;next;//指针后移
delete p ;//释放
</code></pre>
</li>
<li></li>
</ul>
<h2 id="3-3-队列的知识点"><a href="#3-3-队列的知识点" class="headerlink" title="3.3 队列的知识点"></a>3.3 队列的知识点</h2><ul>
<li><p>front 队头，rear队尾</p>
</li>
<li><p>假溢出：q.rear = MAXNSIZE当做队满条件，会存在还有可以存放元素位置的地方，解决办法：循环队列</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/19/203103-111988.jpeg" alt="img"></p>
</li>
<li><p>循环队列</p>
</li>
</ul>
<p>  <img src="https://gitee.com/moluggg/image/raw/master/img/202102/23/171839-101678.jpeg" alt="img"></p>
<p>  判断条件：初始时: q.front = q.rear = 0 </p>
<p>  队首指针进1 ： q.front =(q.front+1)%Maxsize</p>
<p>  队尾指针出1 ：q.rear = (q.rear+1)%Maxsize </p>
<p>  队列长度：（q.rear+Maxsize -q.front)%Maxsize</p>
<p>  为了区分队满与队空的方法：</p>
<p>  ① 少使用一个空间：队满条件就是： （q.rear+1)%Maxsize ==q.front</p>
<p>  ② 增加 统计元素个数的成员Q.size ,队满条件就是： q.size == Maxsize </p>
<p>  ③ 增加tag成员 出队时tag=0 ， 入队时 tag =1  </p>
<ul>
<li><p>链式队列：具有队头指针与队尾指针的单链表</p>
</li>
<li><p>双端链表：了解</p>
</li>
</ul>
<h2 id="3-4-栈与队列的应用"><a href="#3-4-栈与队列的应用" class="headerlink" title="3.4 栈与队列的应用"></a>3.4 栈与队列的应用</h2><p>队列</p>
<p>① 主机与外部设备不匹配问题：打印数据缓冲区</p>
<p>② 多用引起的资源竞争问题：CPU资源就绪队列等</p>
<p>③ 层次遍历</p>
<p>栈：</p>
<p>① 递归</p>
<p>② 遍历（后续遍历等）</p>
<h1 id="第四章-串"><a href="#第四章-串" class="headerlink" title="第四章 串"></a>第四章 串</h1><h2 id="4-1-串的存储方式"><a href="#4-1-串的存储方式" class="headerlink" title="4.1 串的存储方式"></a>4.1 串的存储方式</h2><p>1.定长顺序存储：</p>
<p>地址连续的存储单元存储字符序列</p>
<p>串的长度只能小于等于MAXSIZE 否则 发生截断（截断后面的还是前面的？）</p>
<pre><code class="lang-c++">typedef struct &amp;#123;
 char ch[MAXNSIZE];
 int length ;
&amp;#125;SString ;
</code></pre>
<p>2.堆分配存储表示：<br>地址连续的存储单元存储字符序列。存储空间是动态分配的</p>
<pre><code class="lang-c++">typedef struct &amp;#123;
char *ch;
int length;
&amp;#125;SString ;
</code></pre>
<p>3.块链存储表示：</p>
<p>类似链式存储结构 ，有n个结点连起来 ，通常最后一个结点 占不满，用# 填充</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/23/200119-510473.png" alt="img"></p>
<h2 id="4-2-KMP算法"><a href="#4-2-KMP算法" class="headerlink" title="4.2 KMP算法"></a>4.2 KMP算法</h2><p>1.暴力匹配算法：</p>
<pre><code class="lang-c++">int  i =0 ,j = 0 ;
while(i&lt;S.length()&amp;&amp;j&lt;T.length())&amp;#123;//S是主串
    if (S[i] == T[j]) i++,j++;
    else &amp;#123;
        i =  i- j +1 ;//暴力匹配算法的核心
        j =0 ;
        //若起始位置是 1,1 则 i = i-j+2 ;j =1 ;
    &amp;#125;
&amp;#125;
if (j&gt;=T.length()) return i-T.length();
</code></pre>
<p>2.kmp算法概括：</p>
<p>原理：</p>
<p>字符串中存在大量重复性的子串，暴力匹配造成大量的重复比较的动作，</p>
<p>引入KMP，将对于当前匹配失败之前已经匹配成功 长度 为m的字符串 ，  </p>
<p><strong>寻找小于 m的最长公共前后缀 ，将前缀子串直接移动到 后缀子串的位置</strong> 后比较 </p>
<p>1 2 3 4 5 6 7 8 9</p>
<p><strong>A B</strong> B <strong>A B</strong> C D C A </p>
<p><strong>A B</strong> B <strong>A B</strong> A</p>
<p>在6处匹配失败，之前成功匹配的字符串L15中，将 1-2 直接移动到 4-5位置</p>
<p>如何判断移动到哪去呢？</p>
<p>利用 next数组：子串的第j个字符与主串匹配失败，子串整体<strong>左移</strong>使第j个字符与 next[j] 位置 对应</p>
<p>这样kmp主程序如下：</p>
<p>与暴力匹配算法只有两个地方不一样</p>
<pre><code class="lang-c++">int KMP(String S ,String T,int next[])&amp;#123;
    int i =1 , j =1 ;
    while(i&lt;S.length()&amp;&amp;j&lt;T.length())&amp;#123;
        if(S[i]==T[j]||j==0) i++,j++;//这里的j==0怎么理解？
        else j=next[j];
    &amp;#125;
    if(j&gt;T.length()) return i-T.length();
    else return 0 ;
&amp;#125;
</code></pre>
<p>3.next数组</p>
<p>手算求解办法：<a target="_blank" rel="noopener" href="https://blog.csdn.net/m0_37482190/article/details/86667059">https://blog.csdn.net/m0_37482190/article/details/86667059</a></p>
<pre><code class="lang-c++">void get_next(String T ,int next[])&amp;#123;
   int i=1 ,j =0 ;
   while(i&lt;T.length())&amp;#123;
    //若 p i==pj ,则 next[j+1] = next[j]+1 没看懂 
       if (j==0||T[i]==T[j]) i++,j++,next[i]= j ;
       else j = next[j];
   &amp;#125;
&amp;#125;
</code></pre>
<p>4.nextval数组：</p>
<p>解决类似出现 连续字符，next数组依然需要挨个比较 的问题</p>
<p>该位置i与next[i]元素比较，不同为next[i]值</p>
<p>相同则递归 比较 next[i]与 next[next[i]] 的值，直到不同或者nextval[k] = 0 </p>
<pre><code class="lang-c++">void get_next(String T ,int next[])&amp;#123;
   int i=1 ,j =0 ;
   while(i&lt;T.length())&amp;#123;
    i++,j++;
       if (j==0||T[i]==T[j]) nextval[i]= j ;
       else nextval[i]= nextval[j];
   &amp;#125;
    else j = nextval[j];
&amp;#125;
</code></pre>
<h1 id="第五章-树"><a href="#第五章-树" class="headerlink" title="第五章 树"></a>第五章 树</h1><p>关键词：树 二叉树 遍历二叉树 线索二叉树  排序二叉树 平衡二叉树  树的存储 森林 森林树与二叉树的转换 并查集 哈夫曼树</p>
<h2 id="5-1-树："><a href="#5-1-树：" class="headerlink" title="5.1 树："></a>5.1 树：</h2><p>1.定义：</p>
<p>n= 0 为空树</p>
<p>n&gt;=1 有且只有一个根节点,且其余节点为互不相交的有限集合，且每一个集合本身又是一棵树</p>
<p>2.树的高度与深度区别：深度是从根节点向下，高度是从叶节点向上。</p>
<p>3.树的基本性质：（对照 二叉树的性质）</p>
<p> ① 节点数 = 所以叶子节点的度数 +1 </p>
<p>② 度数 为m的数在第 i层 至多有 $m^{i-1}$</p>
<p>③ 高度 为h 的 m叉树至多 有$(m^{h}-1)(m-1)$个结点</p>
<h2 id="5-2-二叉树"><a href="#5-2-二叉树" class="headerlink" title="5.2 二叉树"></a>5.2 二叉树</h2><p>1.定义：</p>
<p>n=0,空二叉树</p>
<p>n&gt;=1 ,有且只有一个根节点和两个互不相交的集合，分别为左子树和右子树</p>
<p>2.与度数为2的区别：</p>
<p>二叉树可以为空树，度数为2的树得至少3个结点</p>
<p>度数为2的树无严格的左右之分，比如只有一个孩子的树，二叉树必须确定是左孩子还是右孩子</p>
<p>3.满二叉树与完全二叉树</p>
<p>4.二叉树性质：</p>
<p> ① 节点数 = 所以叶子节点的度数 +1 </p>
<p>② 在第 i层 至多有 $2^{i-1}$</p>
<p>③ 高度 为h 的 2叉树至多 有$(2^{h}-1)$个结点</p>
<p>④具有n个结点的完全二叉树 深度为 $Llog_2nJ+1$</p>
<p>5.二叉树的存储结构：</p>
<p>①顺序存储：自上而下，从左到右，适合完全二叉树与满二叉树</p>
<p>②二叉链表</p>
<p>③ 三叉链表（线索链表）</p>
<h2 id="5-3-遍历二叉树，线索二叉树"><a href="#5-3-遍历二叉树，线索二叉树" class="headerlink" title="5.3 遍历二叉树，线索二叉树"></a>5.3 遍历二叉树，线索二叉树</h2><h3 id="5-3-1-遍历二叉树"><a href="#5-3-1-遍历二叉树" class="headerlink" title="5.3.1 遍历二叉树"></a>5.3.1 遍历二叉树</h3><p>1.遍历的本质:将二叉树线性化的过程 ，转化成线性序列</p>
<p>2.先序中序后序遍历：根 左 右   左 根 右  左 右 根</p>
<p>:100: 代码的实现：</p>
<p>有递归与非递归两种算法,非递归实现的思路:</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202103/05/113954-515448.png" alt="img"></p>
<p>先序遍历建立二叉链表，计算二叉树深度，复制二叉树,统计结点个数：</p>
<p>3.由遍历序列 构造二叉树：</p>
<p>先序遍历和中序遍历 可以唯一确定一棵二叉树</p>
<p>后序遍历和中序遍历 也可以唯一确定二叉树</p>
<p>原因是什么？ 对于每一棵树可以确定根节点，以及左子树与右子树，这样递归确定最终的二叉树</p>
<p>!</p>
<h3 id="5-3-2-线索二叉树"><a href="#5-3-2-线索二叉树" class="headerlink" title="5.3.2 线索二叉树"></a>5.3.2 线索二叉树</h3><p>实质：将二叉链表的空指针指向前驱或者后驱</p>
<p>结点的格式：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>lchild</th>
<th>LTag</th>
<th>data</th>
<th>RTag</th>
<th>rchild</th>
</tr>
</thead>
<tbody>
<tr>
<td>左孩子指针</td>
<td>是（1）否（0）左孩子为空</td>
<td>节点数据</td>
<td>是（1）否（0）右孩子为空</td>
<td>右孩子指针</td>
</tr>
</tbody>
</table>
</div>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/23/203146-263519.jpeg" alt="img"></p>
<p>包括三种，前序中序后序线索化树</p>
<p>:100: 代码实现：</p>
<pre><code class="lang-c++">void InTread ( &amp;p , &amp;pre)&amp;#123;

 if(p!=NULL)&amp;#123;
    InTread(p-&gt;lchild,pre);
    if(p-&gt;lchild == NULL)&amp;#123;
        p-&gt;lchild == pre ;
        p-&gt;ltag = 1 ;

    &amp;#125;
    if(pre -&gt;NULL &amp;&amp; pre-&gt;rchild ==NULL)&amp;#123;
        //右指针的赋值是在下一个指针 时线索化，此时 该节点为pre
        pre -&gt; rchild = p;
        pre -&gt; rtag = 1 ;
    &amp;#125;
     InTread(p-&gt;rchild,pre);
&amp;#125;
&amp;#125;
</code></pre>
<h2 id="5-4-排序二叉树-与平衡二叉树"><a href="#5-4-排序二叉树-与平衡二叉树" class="headerlink" title="5.4 排序二叉树 与平衡二叉树"></a>5.4 排序二叉树 与平衡二叉树</h2><h2 id="5-5-树森林"><a href="#5-5-树森林" class="headerlink" title="5.5 树森林"></a>5.5 树森林</h2><h2 id="5-6-树的存储"><a href="#5-6-树的存储" class="headerlink" title="5.6 树的存储"></a>5.6 树的存储</h2><p>双亲表示法：给每一个结点标号，然后将孩子指向双亲</p>
<p>说明：需要连续的存储空间，能确定唯一的双亲，但确定孩子需要遍历整棵树</p>
<p>孩子表示法：给每一个结点标号，然后将孩子结点用单链表连接起来</p>
<p>说明：寻找子女很方便，但是双亲就很麻烦</p>
<p>孩子兄弟表示法：又称为二叉树表示法</p>
<p>每个节点包括：节点值，指向第一个节点的指针，指向下一个兄弟结点的指针</p>
<h2 id="5-7-树的应用"><a href="#5-7-树的应用" class="headerlink" title="5.7 树的应用"></a>5.7 树的应用</h2><p>5.7.1 哈夫曼树</p>
<p>5.7.2 并查集</p>
<h1 id="第六章-图"><a href="#第六章-图" class="headerlink" title="第六章 图"></a>第六章 图</h1><h2 id="6-1-存储结构"><a href="#6-1-存储结构" class="headerlink" title="6.1 存储结构"></a>6.1 存储结构</h2><p>在哪几个方面可以比较：空间复杂度，基本操作（查找邻边 ，删除顶点） </p>
<div class="table-container">
<table>
<thead>
<tr>
<th></th>
<th>说明</th>
<th>空间复杂度</th>
<th>找相临边</th>
<th>删除边与顶点</th>
</tr>
</thead>
<tbody>
<tr>
<td>邻接矩阵</td>
<td>适合于稠密矩阵，能反应各顶点之间的连接关系</td>
<td>O( $n^{2}$)</td>
<td>方便 o(V)</td>
<td>边方便，顶点不方便</td>
</tr>
<tr>
<td>邻接表</td>
<td>（边表和顶点表） 结合顺式存储与链式存储方法，适用于稀疏图，减少空间的浪费</td>
<td>有向图 O(V+E);无向图O(V+2E)</td>
<td>需要遍历整个邻接表</td>
<td>都不方便</td>
</tr>
<tr>
<td>十字链表</td>
<td><strong>有向图</strong>的链式存储结构</td>
<td>O(V+E)</td>
<td>方便</td>
<td>方便</td>
</tr>
<tr>
<td>邻接多重表：</td>
<td>无向图的一种链式存储结构</td>
<td>O(V+E)</td>
<td>方便</td>
<td>方便</td>
</tr>
</tbody>
</table>
</div>
<p>邻接矩阵：适合于稠密矩阵，能反应各顶点之间的连接关系</p>
<p>​                    空间复杂度O( $n^{2}$),寻找邻边不方便 ，</p>
<p>邻接表： 某一个点出度指向的点依次相连形成链式结构</p>
<p>​       计算某两个点是否相连不能直接得出，<strong>出度</strong>计算方便，计算<strong>入度</strong>得用逆邻接表</p>
<p><strong>十字链表</strong>： <strong>有向图</strong>的链式存储结构</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/19/153239-688589.png" alt="image-20210130163046685"></p>
<p>firstin   指向该定点作为<strong>弧头</strong> 的第一条弧</p>
<p>firstout 指向该定点作为<strong>弧尾</strong> 的第一条弧</p>
<p>:100: <strong>如何实现呢？</strong></p>
<p>邻接多重表：无向图的一种链式存储结构</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/19/153248-836462.png" alt="image-20210130163831331"></p>
<p>:100: <strong>如何实现呢？</strong>（理解代码就行）</p>
<p>进行边，点的删除操作 09:00</p>
<h2 id="6-2-图的遍历"><a href="#6-2-图的遍历" class="headerlink" title="6.2 图的遍历"></a>6.2 图的遍历</h2><p>DFS 与BFS ：</p>
<p>空间复杂度：O(|V|)</p>
<p>时间复杂度：采用邻接矩阵是O($|V|^2$ )，采用邻接表示O(|V|+|E|)</p>
<h2 id="6-3-图的应用"><a href="#6-3-图的应用" class="headerlink" title="6.3 图的应用"></a>6.3 图的应用</h2><h3 id="6-3-1-最小生成树"><a href="#6-3-1-最小生成树" class="headerlink" title="6.3.1 最小生成树"></a>6.3.1 最小生成树</h3><p><strong>1.特点：</strong></p>
<p>包含图中所有顶点，且含有尽可能少的边</p>
<p>边数= 顶点数-1 </p>
<p>最小生成树不唯一，权值之和唯一</p>
<p><strong>2.求解算法：</strong></p>
<p>prim 与 kruskal</p>
<p>简述两种算法的原理，思想，步骤，代码的实现：</p>
<p>原理:贪心算法</p>
<p>思想：</p>
<p>从某一个顶点开始，循环执行：选择当前<strong>与已选择的顶点集合</strong>相连的没有加入树的<strong>权值最小</strong>的顶点加入树，这样顶点全部在已选择的顶点集合停止</p>
<p>kruskal :</p>
<p>将边的权值排序，选择当前最短边加入树，并满足加入该边不成环 这样一直到 树里含有n-1条边为止</p>
<p>:100: 代码实现：</p>
<p><strong>3.应用：</strong></p>
<p>城市道路的修建，再怎么修路使得几个城市能相互到达且修路费用最低</p>
<p>（使得结点相互连通且loss最小）</p>
<h3 id="6-3-2-最短路径"><a href="#6-3-2-最短路径" class="headerlink" title="6.3.2  最短路径"></a>6.3.2  最短路径</h3><p><strong>1.两点之间的最短距离以及路径</strong></p>
<p><strong>2.求解算法：</strong></p>
<p>Dijkstra 与 Floyd 算法原理，思想，步骤，代码的实现：</p>
<p>Dijkstra算法：</p>
<p><strong>本质归为贪心算法</strong></p>
<p>初始化操作： vis path dis三个数组，分别记录顶点是否被访问，路径 以及 当前到该顶点的最短距离。初始化 vis  为未访问，初始化dis为 v0到所有顶点的长度，不相连置正无穷</p>
<p>循环执行n-1次：</p>
<p>从一顶点v1出发，找出与该顶点相连的顶点 ，更新当前从v0经过v1到每个顶点的最短路径，选择最短路的顶点作为一条路径点，vis置已访问 </p>
<p>==Floyd== ：</p>
<p><strong>是一种动态规划</strong></p>
<p>任意两点之间的最短距离</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/19/153259-101399.png" alt="image-20210201103419712"></p>
<p>初始化 A为两点之间的有向距离，path 是 i —&gt; j  经过什么点 当前的路径最短 </p>
<p>循环判断 n-1次：</p>
<p>​      每次 对于$ i != j ,i!= v ,j!=v $  的边 进行判断： i经过v点到达j比之前 是否更短 </p>
<p>​      即 $A[i][j] &gt; A[i][v]+A[v][j]$ </p>
<p>证明：</p>
<p>假设$A_{k}(i,j)$表示不经过比k大的中间结点的i,j,之间的最短路径</p>
<p>首先，为了实现这个假设 ，采用一个递推式   ：</p>
<p>$A_{k}(i,j)$ 要么  继承$A_{k-1}(i,j)$ 要么是 $A_{k-1}(i,k)+A_{k-1}(k,j)$ 比前者更优秀 </p>
<p>也就是  $A_{k}(i,j)=min(A_{k-1}(i,j),A_{k-1}(i,k)+A_{k-1}(k,j))$ </p>
<p>这句话说明，对于 $A_{n}(i,j)&lt;= A_{k}(i,j)$ </p>
<blockquote>
<p><strong>Dijkstra  与 prim的比较：</strong></p>
<p>Dijkstra算法用于构建<strong><a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Shortest-path_tree">单源点的最短路径树</a></strong>(MST),Prim算法用于构建<strong><a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Minimum_spanning_tree">最小生成树</a></strong></p>
</blockquote>
<h3 id="6-3-4-拓扑排序"><a href="#6-3-4-拓扑排序" class="headerlink" title="6.3.4 拓扑排序"></a>6.3.4 拓扑排序</h3><p>1.特点：</p>
<p>有向无环图，结点出现只能一次</p>
<blockquote>
<p>AOV网络：表示结点活动的网络，用来表示结点发生的先后顺序</p>
</blockquote>
<p>2.步骤：</p>
<p>每一次选择 入度为0 的结点放入栈中 ，</p>
<p>出栈 ， 放到拓扑队列中，并将 该点与之指向的结点的入度-1  ，并将每一次选择 入度为0 的结点放入栈中 。</p>
<p>这样循环 n次即可</p>
<blockquote>
<p>逆拓扑排序了解一下</p>
</blockquote>
<p>:100:拓扑排序的代码实现：</p>
<p><strong>3.应用：</strong></p>
<p><strong>判断是否有回路：dfs 与拓扑排序</strong></p>
<p>求解关键路径</p>
<p><a target="_blank" rel="noopener" href="https://www.zhihu.com/question/39748146">语音识别中的应用</a>：</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/wangrongrongwq/article/details/114376673">tensorflow数据流图</a></p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202103/11/113055-306258.jpeg" alt="img"></p>
<h3 id="6-3-4-关键路径"><a href="#6-3-4-关键路径" class="headerlink" title="6.3.4 关键路径"></a>6.3.4 关键路径</h3><p>1.特点：</p>
<p>与结点之前连接的所有活动做完才可以进行该节点以及以后的活动（也是拓扑排序的特点）</p>
<p>AOE网络，与AOV网络区别：</p>
<blockquote>
<p>顶点表示事件，有向边表示活动的网络AOE</p>
</blockquote>
<p>2.求解算法：</p>
<p>拓扑排序</p>
<p>对于事件，也就是结点，</p>
<p>最早发生时间：按照拓扑排序 以此  <strong>max</strong></p>
<p>最晚发生时间：按照逆拓扑排序 ，依次 <strong>min</strong></p>
<p><strong>最早与最晚发生时间一样的是关键事件</strong></p>
<p>对于活动，也就是过程ak  i—-&gt;j 为 <i,j></p>
<p>最早发生时间： vi最早发生时间</p>
<p>最晚发生时间： vj最晚发生时间 - ak 权值</p>
<p>时间余量   ：   $活动最晚-最早发生时间$</p>
<p><strong>时间余量为0 就是关键活动，也就是 最早与最晚时间一样的</strong></p>
<p>3.应用：</p>
<p>评估一个项目完成最短时间，求出能够影响整个工程的关键路径</p>
<h3 id="6-3-5-有向无向图描述表达式"><a href="#6-3-5-有向无向图描述表达式" class="headerlink" title="6.3.5 有向无向图描述表达式"></a>6.3.5 有向无向图描述表达式</h3><h1 id="第七章-查找"><a href="#第七章-查找" class="headerlink" title="第七章 查找"></a>第七章 查找</h1><h2 id="7-1-顺序与折半查找"><a href="#7-1-顺序与折半查找" class="headerlink" title="7.1 顺序与折半查找"></a>7.1 顺序与折半查找</h2><h2 id="7-2-分块查找"><a href="#7-2-分块查找" class="headerlink" title="7.2 分块查找"></a>7.2 分块查找</h2><p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/19/151817-474283.png" alt="image-20210202102438958"></p>
<p>1.基本思想：</p>
<p>将查找表分成若干个子块，块内无序，块间有序（第一个块的最大关键字小于第二个块的最小关键字）</p>
<p>2.查找方法： </p>
<p>可以结合顺序与折半查找的方法，进行两层查找。如歌折半查找 30 </p>
<p><strong>首先折半查找 关键字 ， 然后折半查找 块内元素</strong></p>
<p>3.平均找找长度 ：</p>
<p>   $ASL  = L_{关键字长度} + L_{块内元素长度}$</p>
<p>L表示查利用某种方法的平均查找长度   ：</p>
<p>比如顺序，关键字有 5 个 ，则  $L_{关键字长度} = (1+2…+5)/5$</p>
<h2 id="7-3-B树（多路平衡查找树）"><a href="#7-3-B树（多路平衡查找树）" class="headerlink" title="7.3 B树（多路平衡查找树）"></a>7.3 B树（多路平衡查找树）</h2><p>所有结点的孩子的个数的最大值就是B树的阶</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/02/103950-168345.png" alt="image-20210202103949411"></p>
<p>查找描述：（自己总结的）</p>
<p>从 B树的根节点出发，在结点的有序表中进行查找，执行如下操作：</p>
<p>①若 Ki 关键字小于 该查询值 ， 继续查找</p>
<p>②ki等于 该值 ，查找成功；</p>
<p>③ki大于该值 ， 查找 ki左边指针指向的子树 结点并继续查找</p>
<p>④若遍历到结点最后一个关键字 ，查找 ki右边指针指向的子树 结点并继续查找</p>
<p>这样若一直查找到叶节点时，继续查找到失败结点则<strong>查找失败</strong></p>
<p>:100: <strong>B树的插入与删除？</strong></p>
<p>如何保证 查找效率</p>
<p>做一个人为规定 ： </p>
<p>① 对于m叉查找树 ，  任何结点 至少含有  m/2 个分叉 ，（向上取整） ，即  m/2  -1 个关键字 </p>
<p>② 比平衡树更严格 ， 任何一个结点 所有子树的高度必须相同</p>
<p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/02/105245-140913.png" alt="image-20210202105244359"></p>
<h2 id="7-4-B-树"><a href="#7-4-B-树" class="headerlink" title="7.4 B+ 树"></a>7.4 B+ 树</h2><p><img src="https://gitee.com/moluggg/image/raw/master/img/202102/19/153313-134836.png" alt="image-20210202115128774"></p>
<p>与B树的区别：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th></th>
<th>B</th>
<th>B+</th>
</tr>
</thead>
<tbody>
<tr>
<td>关键字与分支</td>
<td>n关键字对应n+1分支</td>
<td>n关键字对应n分支</td>
</tr>
<tr>
<td>关键字数量</td>
<td>叶子结点不包含关键字，不重复</td>
<td>叶子结点包含全部关键字</td>
</tr>
<tr>
<td>结点的作用</td>
<td>B树的任何结点都包含了关键字以及记录的存储地址（也是有记录的）</td>
<td>非叶子结点的作用是索引作用，只有最大关键字以及指向子树的指针，没有关键字的存储地址</td>
</tr>
<tr>
<td>关键字个数取值范围</td>
<td>m/2 -1   &lt; n&lt; m-1(m/2 向上取整)</td>
<td>m/2    &lt; n&lt; m(m/2 向上取整)</td>
</tr>
</tbody>
</table>
</div>
<p>:100: 查找与磁盘块 读取的操作的关系？</p>
<p>文件管理</p>
<h2 id="7-5-散列表："><a href="#7-5-散列表：" class="headerlink" title="7.5 散列表："></a>7.5 散列表：</h2><p>通常的散列函数有哪几种？</p>
<p>处理冲突的方式有哪几种？ </p>
<p>失败与成功查找分母不一样，成功与失败查找率要明确</p>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2572876783@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">💰</a>
</p>






    
        <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
    });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
        src="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<input type="hidden" id="MathJax-js"
        value="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</input>
    




    </div>
    <div class="copyright">
        <p class="footer-entry">
    ©2016-2020 MOLU
</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<a class="" id="rocket" ></a>

    </div>
</div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>Help us with donation</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">alipay</label></span><span><label><input type="radio" name="pay" value="weixin">weixin</label></span>
    </div>
</div>


</body>
<script src="/js/jquery.pjax.js?v=1.1.0" ></script>

<script src="/js/script.js?v=1.1.0" ></script>
<script>
    var img_resize = 'default';
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $("#post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>







</html>
